package main.xht;

import java.util.*;

/**
 * @Author: 谢焕涛
 * @Description: 总采购数 = Σ(SKU卖数 * 提示补货数 / (UX单位配比/货源单位配比) )
 * @Date: 2025/5/23 下午5:38
 * @Version: 1.0
 */
public class CriticalEquationSolver {

    public static void main(String[] args) {
        // 示例输入：方程系数和目标值
        double[] coefficients = {1/20.0, 3/20.0, 10/20.0}; // 例如 1/20, 1/33, 3/20
        double[] coefficients1 = {1, 1, 1};
        double a = 1.0;                                   // 目标值
        solveCriticalSolutions(coefficients, coefficients1, a);
    }

    public static void solveCriticalSolutions(double[] n, double[] n1, double a) {
        final int SCALE = 1000; // 小数精度控制（三位小数）
        int k = n.length;

        // 1. 输入验证和整数转换
        int[] N = new int[k];
        int sumMin = 0;
        for (int i = 0; i < k; i++) {
            if (n[i] < 0.001) {
                System.out.println("错误：所有系数必须 ≥ 0.001");
                return;
            }
            N[i] = (int) Math.round(n[i] * SCALE); // 放大为整数
            sumMin += N[i]; // 每个变量取最小值 xi=1 时的总和
        }

        int A = (int) Math.round(a * SCALE); // 放大后的目标值
        int A_prime = A - sumMin;            // 转换后的目标值

        if (A_prime < 0) {
            System.out.println("无解：变量取最小值时已超过目标值");
            return;
        }

        // 2. 动态规划表初始化
        Map<Integer, List<int[]>> dp = new HashMap<>();
        dp.put(0, new ArrayList<>());
        dp.get(0).add(new int[k]); // 初始解：所有 xi' = 0（对应 xi=1）

        // 3. 动态规划填表
        for (int i = 0; i < k; i++) {
            int Ni = N[i];
            Map<Integer, List<int[]>> newDp = new HashMap<>();

            for (Map.Entry<Integer, List<int[]>> entry : dp.entrySet()) {
                int currentSum = entry.getKey();
                List<int[]> combs = entry.getValue();

                for (int[] comb : combs) {
                    int maxM = (A_prime - currentSum) / Ni; // 最大可添加次数
                    for (int m = 0; m <= maxM; m++) {
                        int newSum = currentSum + m * Ni;
                        int[] newComb = Arrays.copyOf(comb, k);
                        newComb[i] += m;

                        if (newSum > A_prime) break; // 剪枝

                        newDp.computeIfAbsent(newSum, key -> new ArrayList<>()).add(newComb);
                    }
                }
            }
            dp = newDp;
        }

        // 4. 收集所有等于目标的解
        List<int[]> solutions = dp.getOrDefault(A_prime, new ArrayList<>());

        // 5. 过滤临界解：任意变量加1后总和 ≠ A_prime
        List<int[]> criticalSolutions = new ArrayList<>();
        for (int[] comb : solutions) {
            boolean isCritical = true;
            for (int i = 0; i < k; i++) {
                int tempSum = 0;
                for (int j = 0; j < k; j++) {
                    tempSum += (j == i) ? N[j] * (comb[j] + 1) : N[j] * comb[j];
                }
                if (tempSum == A_prime) { // 存在变量加1后仍满足等式
                    isCritical = false;
                    break;
                }
            }
            if (isCritical) criticalSolutions.add(comb);
        }

        // 6. 转换为原始变量并输出
        if (criticalSolutions.isEmpty()) {
            System.out.println("无满足临界条件的解");
        } else {
            System.out.println("临界解（共 " + criticalSolutions.size() + " 种）：");
            for (int[] comb : criticalSolutions) {
                boolean flag = true;
                String str = ("x = [");
                for (int i = 0; i < k; i++) {
                    str = str + ((comb[i] + 1) + (i < k - 1 ? ", " : ""));
                    if ((comb[i] + 1) <  n1[i]){
                        flag = false;
                    }
                }
                str = str +("]");
                if (flag) {
                    System.out.println(str);
                }
            }
        }
    }
}
